﻿#define _CRT_SECURE_NO_WARNINGS 1
#include "stack.h"
#include "queue.h"
#include <algorithm>
#include <queue>
#include "PiorityQueue.h"
//#include <iostream>
//#include <stack>
//#include <queue>
//#include <list>
//using namespace std;
//int main()
//{
//	queue < int> qu;
//	qu.push(1);
//	qu.push(2);
//	qu.push(3);
//	qu.push(4);
//	while (!qu.empty())
//	{
//		cout << qu.front() << " ";
//		qu.pop();
//	}
//	cout << endl;
//	return 0;
//}

//struct ValCount
//{
//	int value;
//	int count;
//};

//int main()
//{
//	stack<int> st;
//	st.push(1);
//	st.push(2);
//	st.push(3);
//	st.push(4);
//	//遍历数据只能边出边看
//	while (!st.empty())
//	{
//		cout << st.top() << " ";
//		st.pop();
//	}
//	cout << endl;
//	return 0;
//}

//int main()
//{
//	int array[] = { 1, 2, 3, 4, 0, 5, 6, 7, 8, 9 };
//	int n = sizeof(array) / sizeof(int);
//	list<int> mylist(array, array + n);
//	auto it = mylist.begin();
//	while (it != mylist.end())
//	{
//		if (*it != 0)
//			cout << *it << " ";
//		else
//			it = mylist.erase(it);
//		++it;
//	}
//	return 0;
//}
void stack_test()
{
	//hao::stack<int, vector<int>> s;
	//hao::stack<int, list<int>> s;
	hao::stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);
	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}
	cout << endl;
}
void queue_test()
{
	hao::queue<int,list<int>> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
}

void test_op1()
{
	srand(time(0));
	const int N = 1000000;

	deque<int> dq;
	vector<int> v;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		v.push_back(e);
		dq.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	sort(dq.begin(), dq.end());
	int end2 = clock();

	printf("vector:%d\n", end1 - begin1);
	printf("deque:%d\n", end2 - begin2);
}

void test_op2()
{
	srand(time(0));
	const int N = 1000000;

	deque<int> dq1;
	deque<int> dq2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand() + i;
		dq1.push_back(e);
		dq2.push_back(e);
	}

	int begin1 = clock();
	sort(dq1.begin(), dq1.end());
	int end1 = clock();

	int begin2 = clock();
	// 拷贝到vector
	vector<int> v(dq2.begin(), dq2.end());
	sort(v.begin(), v.end());
	dq2.assign(v.begin(), v.end());
	int end2 = clock();

	printf("deque sort:%d\n", end1 - begin1);
	printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}
void priority_queue_test()
{
	//小堆的话就需要用仿函数来控制
	priority_queue<int> pq;
	pq.push(1);
	pq.push(12);
	pq.push(31);
	pq.push(4);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}
void my_priority_queue_test()
{
	//int arr[] = { 4,2,5,7,9,1,3,6,8,10 };
	int arr[] = { 1,4,2,5,6,3,2 };
	wang::priority_queue<int> pq1(arr, arr + sizeof(arr) / sizeof(arr[0]));
	/*while (!pq1.empty())
	{
		cout << pq1.top() << " ";
		pq1.pop();
	}*/
	cout << endl;
	wang::priority_queue<int> pq;
	pq.push(1);
	pq.push(12);
	pq.push(31);
	pq.push(4);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}
//less仿函数 - 仿照函数是一个类
//这个类型的对象可以像函数一样去使用,因为它重载了operator()。
//template <class T> 
//struct Less 
//{
//	//重载的是(),这个()是函数调用后面的括号
//	bool operator() (const T& x, const T& y) const 
//	{ 
//		return x < y; 
//	}
//};
//template <class T>
//struct Greater
//{
//	//重载的是(),这个()是函数调用后面的括号
//	bool operator() (const T& x, const T& y) const
//	{
//		return x > y;
//	}
//};
//int main()
//{
//	Less<int> lessFunc;
//	//单看这一行,lessFunc是函数名或者函数指针,只有函数名或者函数指针才能
//	//这么调用,
//	cout << lessFunc(1, 2) << endl;
//	//但是它现在不是函数名或者函数指针,它是一个对象,本质是调用operator()。
//	cout << lessFunc.operator()(1, 2) << endl;
//	return 0;
//}


//int main()
//{
//	int arr[] = { 4,2,5,7,9,1,3,6,8,10 };
//	//想变成小堆就传less，想变成大堆就传greater
//	wang::priority_queue<int,vector<int>> pq(arr,arr+sizeof(arr)/sizeof(arr[0]));
//	while (!pq.empty())
//	{
//		cout << pq.top() << " ";
//		pq.pop();
//	}
//	cout << endl;
//	return 0;
//}

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& _cout, const Date& d);
private:
	int _year;
	int _month;
	int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day;
	return _cout;
}
struct DateLess
{
	bool operator()(const Date* d1, const Date* d2)
	{
		return *d1 < *d2;
	}
};
struct DateGreater
{
	bool operator()(const Date* d1, const Date* d2)
	{
		return *d1 > *d2;
	}
};
void TestPriorityQueue()
{
	//wang::priority_queue<Date> q1;
	//现在这个优先级队列里面存的是节点的指针,这个节点指针树new出来的
	wang::priority_queue<Date*,vector<Date*>, DateGreater> q1;
	q1.push(new Date{2024,10,25});
	q1.push(new Date{2024,2,25 });
	q1.push(new Date{2024,7,25 });
	while (!q1.empty())
	{
		cout << *q1.top() << " ";
		q1.pop();
	}
	cout << endl;
}

int main()
{
	TestPriorityQueue();
	return 0;
}
/*
有的类不支持比较大小,但这个类是别人的,或者库里的,不方便修改
或者这个类支持比较大小,但结果不是想要的,这两种情况我们就可以
提供仿函数,对于自定义类型,我们可以控制顺序的
*/